package com.klun.sort;


import com.klun.Utils.GenUtil;

import static jdk.nashorn.internal.objects.Global.print;

public class QuickSort<T> {

    /**
     * 方式一
     * @param arr
     * @param low
     * @param high
     */
    public void sort(int arr[], int low, int high) {
        int l = low;
        int h = high;
        int povit = arr[low];

        // l<h 没有比对完成
        while (l < h) {
            // 高位坐标值 >= 低位坐标值 高位坐标减一 一直循环直到右面有比 当前值小或相等的值出现
            while (l < h && arr[h] >= povit)
                h--;
            // l < h 位置相同的情况 数据交换
            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                l++;
            }
            // l++(地位的坐标加1) 之后还是小于h
            while (l < h && arr[l] <= povit)
                l++;

            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                h--;
            }
        }
//        print(arr);
//        System.out.print("l=" + (l + 1) + "h=" + (h + 1) + "povit=" + povit + "\n");
        if (l > low) sort(arr, low, l - 1);
        if (h < high) sort(arr, l + 1, high);
    }

    /**
     * 更高效点的代码：方式二
     * @param targetArr
     * @param start
     * @param end
     * @param <T>
     * @return
     */
    public <T extends Comparable<? super T>> T[] quickSort2 (T[] targetArr,int start,int end){
        int i = start + 1, j = end;
        T key = targetArr[start];
        SortUtil<T> sUtil = new SortUtil <T> ();

        if (start >= end) return (targetArr);
        /**
         * 从i++和j--两个方向搜索不满足条件的值并交换
         * 条件为：i++方向小于key，j--方向大于key
         */
        while (true) {
            while (targetArr[j].compareTo(key) > 0){
                j--;
            }
            while (targetArr[i].compareTo(key) < 0 && i < j) {
                i++;
            }
            if (i >= j) break;
            sUtil.swap(targetArr, i, j);
            if (targetArr[i] == key) {
                j--;
            } else {
                i++;
            }
        }

        sUtil.swap(targetArr,start,j); //
        if(start<i-1){
            this.quickSort2(targetArr,start,i-1);
        }
        if(j+1<end){
            this.quickSort2(targetArr,j+1,end);
        }
        return targetArr;
    }

    /**
     * 方式三：减少交换次数，提高效率
     * @param targetArr
     * @param start
     * @param end
     * @param <T>
     */
    private <T extends Comparable<? super T>> void quickSort3(T[] targetArr, int start, int end) {
        int i = start, j = end;
        T key = targetArr[start];

        while (i < j) {
            /*按j--方向遍历目标数组，直到比key小的值为止*/
            while (j > i && targetArr[j].compareTo(key) >= 0) {
                j--;
            }
            if (i < j) {
            /*targetArr[i]已经保存在key中，可将后面的数填入*/
                targetArr[i] = targetArr[j];
                i++;
            }
            /*按i++方向遍历目标数组，直到比key大的值为止*/
            while (i < j && targetArr[i].compareTo(key) <= 0){

            /*此处一定要小于等于零，假设数组之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，
              那么这个小于等于的作用就会使下面的if语句少执行一亿次。*/
                i++;
            }
            if (i < j) {
                /*targetArr[j]已保存在targetArr[i]中，可将前面的值填入*/
                targetArr[j] = targetArr[i];
                j--;
            }
        }

        /*此时i==j*/
        targetArr[i] = key;
        /*递归调用，把key前面的完成排序*/
        this.quickSort3(targetArr,start,i-1);
        /*递归调用，把key后面的完成排序*/
        this.quickSort3(targetArr, j + 1, end);
    }

    /**
     * 第三遍
     * @param arr
     * @param start
     * @param end
     * @param <T>
     * @return
     */
    private <T extends Comparable<? super T>> T[] quickSort6(T[] arr,int start,int end){
        SortUtil<T> sUtil = new SortUtil <T> ();
        int i = start,j = end;
        T key  = arr[i];
        while (true){
            while (arr[j].compareTo(key)>0){j--;}
            while (arr[i].compareTo(key)<0 && i < j){i++; }
            if(i>=j)break;
            /*交换i和j位置上的值*/
            sUtil.swap(arr,start,j);
        }
        if(start<i)quickSort6(arr,start,i);
        if((i+1)<end)quickSort6(arr,i+1,end);
        return arr;
    }


    /**
     * 第七边
     * @param arr
     * @param i
     * @param j
     * @param <T>
     * @return
     */
    private <T extends  Comparable<? super T>> T[] quickSort7(T[] arr,int i,int j){
        if(i>=j)return arr;
        SortUtil<T> sUtil = new SortUtil <T> ();
        int s = i+1;
        int e = j;
        T t = arr[i];
        while(true){
            while (s<e && arr[e].compareTo(t) > 0) {
                e--;
            }
            while (s<e && arr[s].compareTo(t) < 0){
                s++;
            }
            if(s >= e)break;
            sUtil.swap(arr,s,e);
            // 作用?
            if (arr[s] == t) { // 开始的位置==起始值
                e--;
            } else {
                s++;
            }
        }
        sUtil.swap(arr,i,e); //开始位置和结束位置交换
        if(i<=e){
            quickSort7(arr,i,s-1);
        }
        if(j>=e+1){
            quickSort7(arr,e+1,j);
        }
        return arr;
    }

    class SortUtil<T>{
        // 互换位置上的值
        public void swap(T[] targetArr, int i, int j) {
            //TODO
            T t = targetArr[i];
            targetArr[i] = targetArr[j];
            targetArr[j] = t;
        }
    }

    public static void main(String[] args) {
        Integer[] init = GenUtil.genIntArr(10, 1, 10);
        Integer[] integers1 = init;
        Integer[] integers2 = init;
        QuickSort<Integer> sort =  new QuickSort<Integer>();

        int[] a = {3,1,4,9,6,7,2,8,5,7};
//        sort.sort(a,0,9);
        for (int i = 0; i < a.length; i++) {
            Integer integer = a[i];
            System.out.print(integer);
            System.out.print("-");
        }
        System.out.println();

        Integer[] b = {1,3,4,5,6,7,2,4,5,7};
        b =  sort.quickSort7(b,0,9);
        for (int i = 0; i < b.length; i++) {
            Integer integer = b[i];
            System.out.print(integer);
            System.out.print("-");
        }
        System.out.println();



//        /* 生成斐波那契数列 */
//        int[] fbnq = getFBNQ(30);
//        for (int i = 0; i < fbnq.length ;i++) {
//            System.out.print(fbnq[i]);
//            System.out.print(" , ");
//            if(i!= 0 && i%10 == 0){
//                System.out.println();
//            }
//        }
    }

    private static int[] getFBNQ(int length){
        if(length <= 0){
            return null;
        }
        int[] arr = new int[length];
        if(length == 1){
            arr[0] = 1;
            return arr;
        }
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < length; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr;
    }
}